#include<iostream>
using namespace std;

/*
RB树相较于AVL树，其结构并不严格，在插入和删除的效率上远高于AVL树，在查找的效率上略低于AVL树。
同时RB树在计算机领域有着极为广泛的应用，C++STL中多个类型底层都采用了RB树的实现方法。
*/
template<class K,class E>
struct RBTreeNode {
    std::pair<K, E>pair;

    //这里与C++源码统一，使用父节点指针
    //RB树中使用父节点指针可以有效的提升各类操作效率
    RBTreeNode<K,E>* leftChild;
    RBTreeNode<K, E>* rightChild;
    RBTreeNode<K, E>* parent;

    //这里采用bool类型，红色为true，黑色为false
    bool color;
    
    RBTreeNode(std::pair<K, E>& p) {
        pair = p;
        leftChild = nullptr;
        rightChild = nullptr;
        parent = nullptr;
        color = true;
    }
};

template<class K,class E>
class RBTree {
private:
    RBTreeNode<K, E>* root;
    int treeSize;
    void visit(RBTreeNode<K,E>*ptr) {
        if (ptr != nullptr) {
            cout << "Key: " << ptr->pair.first 
                 << " Element: " << ptr->pair.second 
                 << " Color: "<<ptr->color
                 <<endl;
        }
    }
    void dispose(RBTreeNode<K, E>* ptr) {
        if (ptr != nullptr) {
            delete ptr;
        }
    }
    void inOrder(RBTreeNode<K,E>*node);
    void adjust(RBTreeNode<K,E>*&node);
    void adjustXb0(RBTreeNode<K, E>*& node);
public:
    RBTree() {
        root = nullptr;
        treeSize = 0;
    }
    ~RBTree() {
        RBTreeNode<K, E>* ptr = root;
        if (ptr != nullptr) {
            dispose(ptr->leftChild);
            dispose(ptr->rightChild);
            dispose(ptr);
        }
    };
    
    RBTreeNode<K, E>*& getRoot() {
        return root;
    }
    int getTreeSize() {
        return treeSize;
    }
    void ascendOutput(RBTreeNode<K, E>* node) {
        inOrder(root);
    };
    void insert(std::pair<K,E>&p);
    void erase(K&k);
};

template<class K,class E>
void RBTree<K, E>::adjust(RBTreeNode<K,E>*&u) {
    RBTreeNode<K, E>* pu = u->parent;
    //u为根节点或pu为黑色则可以停止
    
    if (u->color == false || pu->color == false)
        return;
    
    RBTreeNode<K, E>* gu = pu->parent;
    
    if (pu == gu->leftChild) {
        //LXr/LXb
        if (gu->rightChild == nullptr || gu->rightChild->color == false) {
            //LXb
            //调整gu(平衡后为gu右孩子)颜色为红色
            if (u == pu->leftChild) {
                //LLb
                RBTreeNode<K, E>* guRight = gu->rightChild;
                RBTreeNode<K, E>* puRight = pu->rightChild;

                gu->rightChild = new RBTreeNode<K, E>(gu->pair);
                gu->rightChild->parent = gu;

                gu->rightChild->rightChild = guRight;
                if(guRight!=nullptr)guRight->parent = gu->rightChild;

                gu->rightChild->leftChild = puRight;
                if (puRight != nullptr)puRight->parent = gu->rightChild;

                gu->leftChild = u;
                u->parent = gu;
                gu->pair = pu->pair;
                delete pu;
                gu->rightChild->color = true;
                return;
            }
            else {
                //LRb
                RBTreeNode<K, E>* guRight = gu->rightChild;
                RBTreeNode<K, E>* uLeft = u->leftChild;
                RBTreeNode<K, E>* uRight = u->rightChild;

                gu->rightChild = new RBTreeNode<K, E>(gu->pair);
                gu->rightChild->parent = gu;

                gu->rightChild->rightChild = guRight;
                if(guRight!=nullptr)guRight->parent = gu->rightChild;

                gu->rightChild->leftChild = uRight;
                if(uRight!=nullptr)uRight->parent = gu->rightChild;

                pu->rightChild = uLeft;
                uLeft->parent = pu;

                gu->pair = u->pair;
                delete u;
                gu->rightChild->color = true;
                return;
            }
        }
        else {
            //LXr
            pu->color = false;
            gu->rightChild->color = false;
            if (gu != root)
                gu->color = true;
            adjust(gu);
        }
    }
    else {
        //RXr/RXb
        if (gu->leftChild == nullptr || gu->leftChild->color == false) {
            //RXb
            //调整gu(平衡后为gu左孩子)颜色为红色
            if (u==pu->rightChild) {
                //RRb
                RBTreeNode<K, E>* guLeft = gu->leftChild;
                RBTreeNode<K, E>* puLeft = pu->leftChild;

                gu->leftChild = new RBTreeNode<K, E>(gu->pair);
                gu->leftChild->parent = gu;

                gu->leftChild->leftChild = guLeft;
                if(guLeft!=nullptr)guLeft->parent = gu->leftChild;

                gu->leftChild->rightChild = puLeft;
                if(puLeft!=nullptr)puLeft->parent = gu->leftChild;

                gu->rightChild = u;
                u->parent = gu;
                gu->pair = pu->pair;
                delete pu;
                gu->leftChild->color = true;
                return;
            }
            else {
                //RLb
                RBTreeNode<K, E>* guLeft = gu->leftChild;
                RBTreeNode<K, E>* uRight = u->rightChild;
                RBTreeNode<K, E>* uLeft = u->leftChild;

                gu->leftChild = new RBTreeNode<K, E>(gu->pair);
                gu->leftChild->parent = gu;

                gu->leftChild->leftChild = guLeft;
                if(guLeft!=nullptr)guLeft->parent = gu->leftChild;

                gu->leftChild->rightChild = uLeft;
                if(uLeft!=nullptr)uLeft->parent = gu->leftChild;

                pu->leftChild = uRight;
                uRight->parent = pu;

                gu->pair = u->pair;
                delete u;
                gu->leftChild->color = true;
                return;
            }
        }
        else {
            //RXr
            pu->color = false;
            gu->leftChild->color = false;
            if (gu != root)
                gu->color = true;
            adjust(gu);
        }
    }
}

template<class K,class E>
void RBTree<K, E>::adjustXb0(RBTreeNode<K, E>*& node) {
    //node表示y的兄弟节点
    RBTreeNode<K, E>* pu = node->parent;
    if (pu->color == false){
        node->color = true;
        RBTreeNode<K, E>* ppu = pu->parent;
        if (ppu == nullptr)
            return;

        if (pu == ppu->leftChild)
            adjustXb0(ppu->rightChild);
        else
            adjustXb0(ppu->leftChild);
    }
    else {
        node->color = true;
        pu->color = false;
        return;
    }
}

template<class K,class E>
void RBTree<K, E>::inOrder(RBTreeNode<K, E>* node) {
    if (node != nullptr) {
        inOrder(node->leftChild);
        visit(node);
        inOrder(node->rightChild);
    }
}

template<class K,class E>
void RBTree<K, E>::insert(std::pair<K, E>& p) {
    RBTreeNode<K, E>* pre=nullptr, * ptr =root;
    while (ptr != nullptr) {
        pre = ptr;
        if (p.first < ptr->pair.first)
            ptr = ptr->leftChild;
        else if (p.first > ptr->pair.first)
            ptr = ptr->rightChild;
        else {
            //查找到此关键字，更新element值
            ptr->pair.second = p.second;
            return;
        }
    }

    RBTreeNode<K, E>* u = nullptr;
    //未查找到此关键字，则作为中断节点的孩子插入树中
    if (root != nullptr) {
        if (p.first < pre->pair.first){
            pre->leftChild = new RBTreeNode<K, E>(p);
            pre->leftChild->color = true;
            pre->leftChild->parent = pre;
            u = pre->leftChild;
        }
        else{
            pre->rightChild = new RBTreeNode<K, E>(p);
            pre->rightChild->color = true;
            pre->rightChild->parent = pre;
            u = pre->rightChild;
        }
    }
    else{
        root = new RBTreeNode<K, E>(p);
        root->color = false;
        return;
    }
    treeSize++;

    RBTreeNode<K, E>* pu = pre;
    if (u->color==false||pu->color==false)
        return;
    
    //进行节点颜色平衡
    adjust(u);
}

template<class K, class E>
void RBTree<K, E>::erase(K&k) {
    RBTreeNode<K, E>* ptr = root;

    //寻找关键字为k的节点
    while (ptr!=nullptr&&ptr->pair.first != k) {
        if (ptr->pair.first < k)
            ptr = ptr->leftChild;
        else
            ptr = ptr->rightChild;
    }

    //未查找到
    if (ptr == nullptr) {
        cout << "No such node whose key is k." << endl;
        return;
    }

    bool isYRightChild = false;//被删除节点是否为父节点的右孩子，区分RXY或LXY

    RBTreeNode<K, E>* py = nullptr;
    RBTreeNode<K, E>* yChild = nullptr;

    //根据实际删除的节点颜色来判断采取哪种操作
    //目标节点双孩子节点都存在
    if (ptr->leftChild != nullptr && ptr->rightChild != nullptr) {
        RBTreeNode<K, E>* y = ptr->leftChild;

        //寻找左前驱
        if (y->rightChild)
            y = y->rightChild;

        py = y->parent;
        yChild = y->leftChild;//可能为空节点

        ptr->pair = y->pair;

        if (y == py->leftChild)
            py->leftChild = yChild;
        else
            py->rightChild = yChild;
        if (yChild)yChild->parent = py;
        
        bool yColor = y->color;
        
        if (y == py->rightChild)isYRightChild = true;

        delete y;

        if(yColor==true)
            return;
    }
    else {
        //目标节点至多仅有1个孩子节点
        py = ptr->parent;

        if (ptr->leftChild)
            yChild = ptr->leftChild;
        else
            yChild = ptr->rightChild;

        //ptr为根节点
        if (py == nullptr) {
            root = yChild;
            yChild->color = false;
            delete ptr;
            return;
        }

        if (ptr == py->leftChild)
            py->leftChild = yChild;
        else
            py->rightChild = yChild;
        if(yChild)yChild->parent = py;

        RBTreeNode<K, E>* y = ptr;
        bool yColor = y->color;
        
        if (y == py->rightChild)isYRightChild = true;

        delete y;

        if (yColor == true)
            return;
    }

    //程序运行到此处说明实际被删除节点为黑色
    if (isYRightChild) {
        //RbX/RrX
        //兄弟节点必然存在，否则黑色节点数量不匹配
        RBTreeNode<K, E>* v = py->leftChild;
        RBTreeNode<K, E>* vL = v->leftChild;
        RBTreeNode<K, E>* vR = v->rightChild;
        if (v->color == false) {
            //RbX
            //根据v孩子节点中红色节点的数量分为3种情况
            if (vL != nullptr && vR != nullptr && vL->color == true && vR->color == true) {
                //Rb2
                //同Rb1(ii)
                py->rightChild = new RBTreeNode<K, E>(py->pair);
                py->rightChild->color = false;
                py->rightChild->parent = py;

                py->rightChild->rightChild = yChild;
                if(yChild)yChild->parent = py->rightChild;

                py->rightChild->leftChild = vR->rightChild;
                if(vR->rightChild)vR->rightChild->parent = py->rightChild->leftChild;

                v->rightChild = vR->leftChild;
                if(vR->leftChild)vR->leftChild->parent = v;

                py->pair = vR->pair;
                delete vR;
            }
            else if ((vL == nullptr && vR == nullptr) ||
                (vL != nullptr && vR != nullptr && vR->color == false && vL->color == false) ||
                (vL == nullptr && vR->color == false) ||
                (vR == nullptr && vL->color == false)
                ) {
                //Rb0
                //pu成为新的y，向上继续调整颜色
                adjustXb0(v);
            }
            else {
                //Rb1
                if (vL != nullptr && vL->color == true) {
                    //Rb1(i)，v的左孩子存在且为红色
                    py->rightChild = new RBTreeNode<K, E>(py->pair);
                    py->rightChild->color = false;
                    py->rightChild->parent = py;

                    py->rightChild->rightChild = yChild;
                    if(yChild)yChild->parent = py->rightChild;

                    py->rightChild->leftChild = vR;
                    vR->parent = py->rightChild->leftChild;

                    py->pair = v->pair;
                    py->leftChild = vL;
                    vL->parent = py;
                    vL->color = false;

                    delete v;
                }
                else {
                    //Rb1(ii)，v的右孩子存在且为红色
                    py->rightChild = new RBTreeNode<K, E>(py->pair);
                    py->rightChild->color = false;
                    py->rightChild->parent = py;

                    py->rightChild->rightChild = yChild;
                    if(yChild)yChild->parent = py->rightChild;

                    py->rightChild->leftChild = vR->rightChild;
                    if(vR->rightChild)vR->rightChild->parent = py->rightChild->leftChild;

                    v->rightChild = vR->leftChild;
                    if(vR->leftChild)vR->leftChild->parent = v;

                    py->pair = vR->pair;
                    delete vR;
                }
            }
        }
        else {
            //RrX
            //vL和vR必然存在，否则黑色节点数量不匹配
            RBTreeNode<K, E>* vRR = vR->rightChild;
            RBTreeNode<K, E>* vRL = vR->leftChild;
            if (vRR = nullptr && vRL = nullptr && vRR->color == true && vRL->color == true) {
                //Rr2
                py->rightChild = new RBTreeNode<K, E>(py->pair);
                py->rightChild->color = false;
                py->rightChild->parent = py;

                py->rightChild->rightChild = yChild;
                if (yChild)yChild->parent = py->rightChild;

                py->rightChild->leftChild = vRR->rightChild;
                if (vRR->rightChild)vRR->rightChild->parent = py->rightChild->leftChild;

                vR->rightChild = vRR->leftChild;
                if (vRR->leftChild)vRR->leftChild->parent = vR;

                py->pair = vRR->pair;

                delete vRR;
            }
            else if ((vRR == nullptr && vRL == nullptr) ||
                (vRR != nullptr && vRL != nullptr && vRR->color == false && vRL->color == false) ||
                (vRR == nullptr && vRL->color == false) ||
                (vRL == nullptr && vRR->color == false)
                ) {
                //Rr0
                py->rightChild = new RBTreeNode<K, E>(py->pair);
                py->rightChild->color = false;
                py->rightChild->parent = py;

                py->rightChild->rightChild = yChild;
                if(yChild)yChild->parent = py->rightChild;

                py->rightChild->leftChild = vR;
                py->rightChild->leftChild->color = true;
                vR->parent = py->rightChild->leftChild;

                py->pair = v->pair;
                py->leftChild = vL;
                vL->parent = py;

                delete v;
            }
            else {
                //Rr1
                if (vRL != nullptr && vRL->color == true) {
                    //Rr1(i)
                    py->rightChild = new RBTreeNode<K, E>(py->pair);
                    py->rightChild->color = false;
                    py->rightChild->parent = py;

                    py->rightChild->rightChild = yChild;
                    if (yChild)yChild->parent = py->rightChild;

                    py->rightChild->leftChild = vRR;
                    if(vRR)vRR->parent = py->rightChild->leftChild;

                    v->rightChild = vRL;
                    vRL->color = false;
                    vRL->parent = v;

                    py->pair = vR->pair;
                    delete vR;
                }
                else {
                    //Rr1(ii)
                    py->rightChild = new RBTreeNode<K, E>(py->pair);
                    py->rightChild->color = false;
                    py->rightChild->parent = py;

                    py->rightChild->rightChild = yChild;
                    if (yChild)yChild->parent = py->rightChild;

                    py->rightChild->leftChild = vRR->rightChild;
                    if (vRR->rightChild)vRR->rightChild->parent = py->rightChild->leftChild;

                    vR->rightChild = vRR->leftChild;
                    if (vRR->leftChild)vRR->leftChild->parent = vR;

                    py->pair = vRR->pair;

                    delete vRR;
                }
            }
        }
    }
    else {
        //LbX/LrX
        //兄弟节点必然存在，否则黑色节点数量不匹配
        RBTreeNode<K, E>* v = py->rightChild;
        RBTreeNode<K, E>* vR = v->rightChild;
        RBTreeNode<K, E>* vL = v->leftChild;
        if (v->color == false) {
            //LbX
            //根据v孩子节点中红色节点的数量分为3种情况
            if (vL != nullptr && vR != nullptr && vL->color == true && vR->color == true) {
                //Lb2
                //同Lb1(ii)
                py->leftChild = new RBTreeNode<K, E>(py->pair);
                py->leftChild->color = false;
                py->leftChild->parent = py;

                py->leftChild->leftChild = yChild;
                if(yChild)yChild->parent = py->leftChild;

                py->leftChild->rightChild = vL->leftChild;
                if(vL->leftChild)vL->leftChild->parent = py->leftChild->rightChild;

                v->leftChild = vL->rightChild;
                if(vL->rightChild)vL->rightChild->parent = v;

                py->pair = vL->pair;
                delete vL;
            }
            else if ((vL == nullptr && vR == nullptr) ||
                    (vL != nullptr && vR != nullptr && vR->color == false && vL->color == false) ||
                    (vL == nullptr && vR->color == false) ||
                    (vR == nullptr && vL->color == false)
                    ) {
                    //Lb0
                    //pu成为新的y，向上继续调整颜色
                    adjustXb0(v);
            }
            else {
                //Lb1(i)，v的右孩子存在且为红色
                if (vR != nullptr && vR->color == true) {
                    //Lb1(i)，v的右孩子存在且为红色
                    py->leftChild = new RBTreeNode<K, E>(py->pair);
                    py->leftChild->color = false;
                    py->leftChild->parent = py;

                    py->leftChild->leftChild = yChild;
                    if(yChild)yChild->parent = py->leftChild;

                    py->leftChild->rightChild = vL;
                    vL->parent = py->leftChild->rightChild;

                    py->pair = v->pair;
                    py->rightChild = vR;
                    vR->parent = py;
                    vR->color = false;

                    delete v;
                }
                else {
                    //Lb1(ii)，v的左孩子存在且为红色
                    py->leftChild = new RBTreeNode<K, E>(py->pair);
                    py->leftChild->color = false;
                    py->leftChild->parent = py;

                    py->leftChild->leftChild = yChild;
                    if(yChild)yChild->parent = py->leftChild;

                    py->leftChild->rightChild = vL->leftChild;
                    if(vL->leftChild)vL->leftChild->parent = py->leftChild->rightChild;

                    v->leftChild = vL->rightChild;
                    if(vL->rightChild)vL->rightChild->parent = v;

                    py->pair = vL->pair;
                    delete vL;
                }
            }
        }
        else {
            //LrX
            //vL和vR必然存在，否则黑色节点数量不匹配
            RBTreeNode<K, E>* vLL = vL->leftChild;
            RBTreeNode<K, E>* vLR = vL->rightChild;
            if (vLL = nullptr && vLR = nullptr && vLL->color == true && vLR->color == true) {
                //Lr2
                py->leftChild = new RBTreeNode<K, E>(py->pair);
                py->leftChild->color = false;
                py->leftChild->parent = py;

                py->leftChild->leftChild = yChild;
                if (yChild)yChild->parent = py->leftChild;

                py->leftChild->rightChild = vLL->leftChild;
                if (vLL->leftChild)vLL->leftChild->parent = py->leftChild->rightChild;

                vL->leftChild = vLL->rightChild;
                if (vLL->rightChild)vLL->rightChild->parent = vL;

                py->pair = vLL->pair;

                delete vLL;
            }
            else if ((vLL == nullptr && vLR == nullptr) ||
                     (vLL != nullptr && vLR != nullptr && vLL->color == false && vLR->color == false) ||
                     (vLL == nullptr && vLR->color == false) ||
                     (vLR == nullptr && vLL->color == false)
                    ) {
                    //Lr0
                    py->leftChild = new RBTreeNode<K, E>(py->pair);
                    py->leftChild->color = false;
                    py->leftChild->parent = py;

                    py->leftChild->leftChild = yChild;
                    if(yChild)yChild->parent = py->leftChild;

                    py->leftChild->rightChild = vL;
                    py->leftChild->rightChild->color = true;
                    vL->parent = py->leftChild->rightChild;

                    py->pair = v->pair;
                    py->rightChild = vR;
                    vR->parent = py;

                    delete v;
            }
            else {
                if (vLR != nullptr && vLR->color == true) {
                    //Lr1(i)
                    py->leftChild = new RBTreeNode<K, E>(py->pair);
                    py->leftChild->color = false;
                    py->leftChild->parent = py;

                    py->leftChild->leftChild = yChild;
                    if (yChild)yChild->parent = py->leftChild;

                    py->leftChild->rightChild = vLL;
                    if(vLL)vLL->parent = py->leftChild->rightChild;

                    v->leftChild = vLR;
                    vLR->color = false;
                    vLR->parent = v;

                    py->pair = vL->pair;
                    delete vL;
                }
                else {
                    //Lr1(ii)
                    py->leftChild = new RBTreeNode<K, E>(py->pair);
                    py->leftChild->color = false;
                    py->leftChild->parent = py;

                    py->leftChild->leftChild = yChild;
                    if (yChild)yChild->parent = py->leftChild;

                    py->leftChild->rightChild = vLL->leftChild;
                    if (vLL->rightChild)vLL->leftChild->parent = py->lefttChild->rightChild;

                    vL->leftChild = vLL->rightChild;
                    if (vLL->rightChild)vLL->rightChild->parent = vL;

                    py->pair = vLL->pair;

                    delete vLL;
                }
            }
        }
    }
}

int main() {
    RBTree<int, int>tree;
    std::pair<int, int>* p = new std::pair<int, int>;

    p->first = 20;
    p->second = 12;
    tree.insert(*p);

    p->first = 39;
    p->second = 33;
    tree.insert(*p);

    p->first = 17;
    p->second = 58;
    tree.insert(*p);

    p->first = 14;
    p->second = 93;
    tree.insert(*p);

    p->first = 19;
    p->second = 48;
    tree.insert(*p);

    p->first = 11;
    p->second = 60;
    tree.insert(*p);

    p->first = 9;
    p->second = 70;
    tree.insert(*p);

    tree.ascendOutput(tree.getRoot());
    delete p;
    return 0;
}